package bTree.LeetCode;

import java.util.HashMap;
import java.util.Map;

public class 实现Trie前缀树 {

    class TreeNode {
        Map<Character, TreeNode> children;
        Boolean isEnd;

        public TreeNode() {
            this.children = new HashMap<>();
            this.isEnd = false;
        }
    }

    TreeNode rootNode;

    public Trie() {
        rootNode = new TreeNode();
    }

    public void insert(String word) {
        int length = word.length();
        TreeNode node=rootNode;
        for (int i = 0; i < length ; i++) {
            if (!node.children.containsKey(word.charAt(i))){
                node.children.put(word.charAt(i),new TreeNode());
            }
            node=node.children.get(word.charAt(i));
        }
        //最后一个要置为end;
        node.isEnd=true;
    }

    public boolean search(String word) {
        int length = word.length();
        TreeNode node=rootNode;
        for (int i = 0; i < length; i++) {
            if (!node.children.containsKey(word.charAt(i))){
                return false;
            }
            node=node.children.get(word.charAt(i));
        }
        if (!node.isEnd){
            return false;
        }
        return true;
    }

    public boolean startsWith(String prefix) {
        int length = prefix.length();
        TreeNode node=rootNode;
        for (int i = 0; i < length; i++) {
            if (!node.children.containsKey(prefix.charAt(i))){
                return false;
            }
            node=node.children.get(prefix.charAt(i));
        }
        return true;
    }
}
